/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution{
public:
  TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder){

    TreeNode *p = nullptr;

    build(p, preorder, 0, preorder.size(), inorder, 0, inorder.size());

    return p;

  }

  void build(TreeNode *&cur, vector<int> &preorder, int preStart, int preEnd,
             vector<int> &inorder, int inStart, int inEnd){

    if(preStart >= preEnd || inStart >= inEnd){
      return;
    }

    int i;
    for(i = inStart; i < inEnd; ++i){
      if(inorder[i] == preorder[preStart]){
        break;
      }
    }

    cur = new TreeNode(inorder[i]);
    int leftCnt = i - inStart;
    build(cur->left, preorder, preStart + 1, preStart + leftCnt + 1, inorder, inStart, i);
    build(cur->right, preorder, preStart + leftCnt + 1, preEnd, inorder, i + 1, inEnd);

  }
};